package library;

public class Algorithm {
    //作用：生成下一个排列 (数组范围[l,r])
    //返回值：
    //      1.如果有下一个排列，则返回true，并对传入的数组进行修改
    //      2.如果没有下一个排列（即最后一个排列），则返回false，并生成第一个排列
    public static boolean nextPermutation(int[] arr, int l, int r) {
        return myAlgorithm.nextPermutation(arr, l, r);
    }

    public static boolean nextPermutation(int[] arr) {
        return myAlgorithm.nextPermutation(arr);
    }

    public static boolean nextPermutation(long[] arr, int l, int r) {
        return myAlgorithm.nextPermutation(arr, l, r);
    }

    public static boolean nextPermutation(long[] arr) {
        return myAlgorithm.nextPermutation(arr);
    }

    public static boolean nextPermutation(char[] arr, int l, int r) {
        return myAlgorithm.nextPermutation(arr, l, r);
    }

    public static boolean nextPermutation(char[] arr) {
        return myAlgorithm.nextPermutation(arr);
    }

    /*
     * 作用：求两个数的最大公约数
     * 描述：stein求最大公约数
     * 注意：方法名带前缀_表示保证传入的数字为非负数
     */
    public static int _gcd(int a, int b) {
        return myMath._gcd(a, b);
    }

    public static long _gcd(long a, long b) {
        return myMath._gcd(a, b);
    }

    public static int gcd(int a, int b) {
        return _gcd(Math.abs(a), Math.abs(b));
    }

    public static long gcd(long a, long b) {
        return _gcd(Math.abs(a), Math.abs(b));
    }

    /*
     * 作用：求多个数的最大公约数
     * 注意：方法名带前缀_表示保证传入的数字为非负数
     */
    public static int gcd(int a, int b, int... args) {
        int ans = _gcd(Math.abs(a), Math.abs(b));
        for (int element : args) {
            ans = _gcd(ans, Math.abs(element));
        }
        return ans;
    }

    public static long gcd(long a, long b, long... args) {
        long ans = _gcd(Math.abs(a), Math.abs(b));
        for (long element : args) {
            ans = _gcd(ans, Math.abs(element));
        }
        return ans;
    }

    /*
     * 作用：求两个数的最小公倍数
     * 注意：方法名带前缀_表示保证传入的数字为非负数
     */
    public static int _lcm(int a, int b) {
        return a / _gcd(a, b) * b;
    }

    public static int lcm(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        return a / _gcd(a, b) * b;
    }

    public static long _lcm(long a, long b) {
        return a / _gcd(a, b) * b;
    }

    public static long lcm(long a, long b) {
        a = Math.abs(a);
        b = Math.abs(b);
        return a / _gcd(a, b) * b;
    }

    /*
     * 作用：求多个数的最小公倍数
     * 注意：方法名带前缀_表示保证传入的数字为非负数
     */
    public static int _lcm(int a, int b, int... args) {
        int ans = _lcm(a, b);
        for (int element : args) {
            ans = _lcm(ans, element);
        }
        return ans;
    }

    public static long _lcm(long a, long b, long... args) {
        long ans = _lcm(a, b);
        for (long element : args) {
            ans = _lcm(ans, element);
        }
        return ans;
    }

    public static int lcm(int a, int b, int... args) {
        int ans = lcm(a, b);
        for (int element : args) {
            ans = _lcm(ans, Math.abs(element));
        }
        return ans;
    }

    public static long lcm(long a, long b, long... args) {
        long ans = lcm(a, b);
        for (long element : args) {
            ans = _lcm(ans, Math.abs(element));
        }
        return ans;
    }

    /*
     * 作用：求ax+by=gcd(a,b)的(x,y)的可行解，并返回gcd(a,b)
     * 注意：该gcd可能为负数
     * 描述：由于Java无C++式的引用(&)，所以以数组形式表示(x,y) → (arr[0],arr[1])
     */
    public static int exgcd(int a, int b, int[] arr) {
        return myMath.exgcd(a, b, arr);
    }

    public static long exgcd(long a, long b, long[] arr) {
        return myMath.exgcd(a, b, arr);
    }

    /*
     * 作用：求a在模m意义下的乘法逆元
     * 描述：扩展欧几里得求乘法逆元
     *      若该数不存在在模m意义下的乘法逆元，则抛出异常
     * 注意：方法名带前缀_的为结果可能为负数
     */
    public static int _inv(int a, int m) {
        return myMath._inv(a, m);
    }

    public static long _inv(long a, long m) {
        return myMath._inv(a, m);
    }

    public static int inv(final int a, final int m) {
        int ans = _inv(a, m);
        while (ans < 0) ans += m;
        return ans;
    }

    public static long inv(final long a, final long m) {
        long ans = _inv(a, m);
        while (ans < 0) ans += m;
        return ans;
    }

    /*
     * 作用：交换数组内的两个值
     */
    public static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void swap(long[] arr, int l, int r) {
        long temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void swap(float[] arr, int l, int r) {
        float temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void swap(double[] arr, int l, int r) {
        double temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void swap(char[] arr, int l, int r) {
        char temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    /*
     * 作用：对数组进行划分，选择一个基准pivot，放在它排序后的位置，即左边的数比它小，右边的数比它大
     * 描述：返回基准下标（快速排序所用）
     */
    public static int partition(int[] arr, int l, int r, int pos) {
        int pivot = arr[pos];
        swap(arr, l, pos);
        while (l < r) {
            while (l < r && arr[r] >= pivot) --r;
            arr[l] = arr[r];
            while (l < r && arr[l] <= pivot) ++l;
            arr[r] = arr[l];
        }
        arr[l] = pivot;
        return l;
    }

    /*
     * 作用：对数组进行排序
     * 描述：快速排序
     */
    public static void quickSort(int[] arr, int l, int r) {
        mySort.quickSort(arr, l, r);
    }

    public static void quickSort(long[] arr, int l, int r) {
        mySort.quickSort(arr, l, r);
    }

    public static void quickSort(char[] arr, int l, int r) {
        mySort.quickSort(arr, l, r);
    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(long[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(char[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /*
     * 作用：求最小值
     */
    public static int min(int a, int b) {
        return a < b ? a : b;
    }

    public static long min(long a, long b) {
        return a < b ? a : b;
    }

    public static float min(float a, float b) {
        return a < b ? a : b;
    }

    public static double min(double a, double b) {
        return a < b ? a : b;
    }

    public static int min(int a, int b, int... args) {
        int ans = a < b ? a : b;
        for (int element : args) {
            ans = ans < element ? ans : element;
        }
        return ans;
    }

    public static long min(long a, long b, long... args) {
        long ans = a < b ? a : b;
        for (long element : args) {
            ans = ans < element ? ans : element;
        }
        return ans;
    }

    public static float min(float a, float b, float... args) {
        float ans = a < b ? a : b;
        for (float element : args) {
            ans = ans < element ? ans : element;
        }
        return ans;
    }

    public static double min(double a, double b, double... args) {
        double ans = a < b ? a : b;
        for (double element : args) {
            ans = ans < element ? ans : element;
        }
        return ans;
    }

    public static int min(int[] arr) {
        int ans = Integer.MAX_VALUE;
        for (int element : arr) {
            ans = ans < element ? ans : element;
        }
        return ans;
    }

    public static long min(long[] arr) {
        long ans = Long.MAX_VALUE;
        for (long element : arr) {
            ans = ans < element ? ans : element;
        }
        return ans;
    }

    public static float min(float[] arr) {
        float ans = Float.MAX_VALUE;
        for (float element : arr) {
            ans = ans < element ? ans : element;
        }
        return ans;
    }

    public static double min(double[] arr) {
        double ans = Double.MAX_VALUE;
        for (double element : arr) {
            ans = ans < element ? ans : element;
        }
        return ans;
    }

    public static int min(int[] arr, int l, int r) {
        int ans = Integer.MAX_VALUE;
        while (l <= r) {
            ans = ans < arr[l] ? ans : arr[l];
            ++l;
        }
        return ans;
    }

    public static long min(long[] arr, int l, int r) {
        long ans = Long.MAX_VALUE;
        while (l <= r) {
            ans = ans < arr[l] ? ans : arr[l];
            ++l;
        }
        return ans;
    }

    public static float min(float[] arr, int l, int r) {
        float ans = Float.MAX_VALUE;
        while (l <= r) {
            ans = ans < arr[l] ? ans : arr[l];
            ++l;
        }
        return ans;
    }

    public static double min(double[] arr, int l, int r) {
        double ans = Double.MAX_VALUE;
        while (l <= r) {
            ans = ans < arr[l] ? ans : arr[l];
            ++l;
        }
        return ans;
    }

    /*
     * 作用：求最大值
     */

    public static int max(int a, int b) {
        return a > b ? a : b;
    }

    public static long max(long a, long b) {
        return a > b ? a : b;
    }

    public static float max(float a, float b) {
        return a > b ? a : b;
    }

    public static double max(double a, double b) {
        return a > b ? a : b;
    }

    public static int max(int a, int b, int... args) {
        int ans = a > b ? a : b;
        for (int element : args) {
            ans = ans > element ? ans : element;
        }
        return ans;
    }

    public static long max(long a, long b, long... args) {
        long ans = a > b ? a : b;
        for (long element : args) {
            ans = ans > element ? ans : element;
        }
        return ans;
    }

    public static float max(float a, float b, float... args) {
        float ans = a > b ? a : b;
        for (float element : args) {
            ans = ans > element ? ans : element;
        }
        return ans;
    }

    public static double max(double a, double b, double... args) {
        double ans = a > b ? a : b;
        for (double element : args) {
            ans = ans > element ? ans : element;
        }
        return ans;
    }

    public static int max(int[] arr) {
        int ans = Integer.MIN_VALUE;
        for (int element : arr) {
            ans = ans > element ? ans : element;
        }
        return ans;
    }

    public static long max(long[] arr) {
        long ans = Long.MIN_VALUE;
        for (long element : arr) {
            ans = ans > element ? ans : element;
        }
        return ans;
    }

    public static float max(float[] arr) {
        float ans = Float.MIN_VALUE;
        for (float element : arr) {
            ans = ans > element ? ans : element;
        }
        return ans;
    }

    public static double max(double[] arr) {
        double ans = Double.MIN_VALUE;
        for (double element : arr) {
            ans = ans > element ? ans : element;
        }
        return ans;
    }

    public static int max(int[] arr, int l, int r) {
        int ans = Integer.MIN_VALUE;
        while (l <= r) {
            ans = ans > arr[l] ? ans : arr[l];
            ++l;
        }
        return ans;
    }

    public static long max(long[] arr, int l, int r) {
        long ans = Long.MIN_VALUE;
        while (l <= r) {
            ans = ans > arr[l] ? ans : arr[l];
            ++l;
        }
        return ans;
    }

    public static float max(float[] arr, int l, int r) {
        float ans = Float.MIN_VALUE;
        while (l <= r) {
            ans = ans > arr[l] ? ans : arr[l];
            ++l;
        }
        return ans;
    }

    public static double max(double[] arr, int l, int r) {
        double ans = Double.MIN_VALUE;
        while (l <= r) {
            ans = ans > arr[l] ? ans : arr[l];
            ++l;
        }
        return ans;
    }

    /*
     * 作用：将数组逆序
     */
    public static void reverse(int[] arr, int l, int r) {
        while (l < r) swap(arr, l++, r--);
    }

    public static void reverse(long[] arr, int l, int r) {
        while (l < r) swap(arr, l++, r--);
    }

    public static void reverse(float[] arr, int l, int r) {
        while (l < r) swap(arr, l++, r--);
    }

    public static void reverse(double[] arr, int l, int r) {
        while (l < r) swap(arr, l++, r--);
    }

    public static void reverse(char[] arr, int l, int r) {
        while (l < r) swap(arr, l++, r--);
    }

    public static void reverse(int[] arr) {
        reverse(arr, 0, arr.length - 1);
    }

    public static void reverse(long[] arr) {
        reverse(arr, 0, arr.length - 1);
    }

    public static void reverse(float[] arr) {
        reverse(arr, 0, arr.length - 1);
    }

    public static void reverse(double[] arr) {
        reverse(arr, 0, arr.length - 1);
    }

    public static void reverse(char[] arr) {
        reverse(arr, 0, arr.length - 1);
    }
}
